
//dfs版本
#include<iostream>
using namespace std;
const int N = 10;
int path[N];  //保存序列
int state[N]; //数字是否被用过
int n;
void dfs(int u)
{
    if(u > n)//数字填完了，输出
    {
        for(int i = 1; i <= n; i++) //输出方案
            cout << path[i] << " ";
        cout << endl;
    }

    for(int i = 1; i <= n; i++) //空位上可以选择的数字为:1 ~ n
    {
        if(!state[i])    //如果数字 i 没有被用过
        {
            path[u] = i; //放入空位
            state[i] = 1;//数字被用，修改状态
            dfs(u + 1);  //填下一个位
            state[i] = 0;//回溯，取出 i
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);//从1开始dfs搜索
    return 0;
}



//递推版本
#include <iostream>
using namespace std;

void fun(string s,int l,int r)
{
    if(l==r)//当一遍遍历结束，说明该解成立，则输出
    {
        cout<<s<<endl;//输出结果
        return;//回溯,由于后面没有执行语句，而且void返回，所以这句有没有无所谓，不过return是好习惯
    }

    else
    {
        for(int i=l;i<=r;i++)//从前往后交换，由于i++性质，则不重复
        {
            swap(s[l],s[i]);//交换
            fun(s,l+1,r);//递推，进一步交换
            swap(s[l],s[i]);//回溯复原
        }
    }
}

int main() {
    int n;
    cin >> n;
    string s = "";
    for (char i = '1'; i < '1' + n; i++) {
        s += i;//将不大于‘9’的数字叠加进字符串，int数组同理，目的是为了生成所有数字
    }
    fun(s, 0, n - 1);//从头开始遍历
}